package sort.heap;

import sort.common.PrintArr;
import sort.common.SortClass;

import java.util.Arrays;

/**
 * 堆排序
 * 堆--完全二叉树，用数组表示： 索引是从0开始，i个节点的左右孩子分别为 2*i+1 和 2*i+2
 * 用于堆排序 或者 优先队列
 *  i个节点的左右孩子分别为 2*i+1 和 2*i+2，根节点储存在数组0号位置
 */
public class HeapSort extends PrintArr implements SortClass {


    @Override
    public void sort(int[] arr) {
        //1.建堆,这里元素的索引是从0开始的,所以最后一个非叶子结点array.length/2 - 1
        for (int i = arr.length/2 -1; i >=0 ; i--) {
            heapify(arr,i,arr.length);
        }
        //2.排序： 依次弹出堆顶元素
        for (int j = arr.length-1; j >=0 ; j--) {
            swap(arr,j,0);
            heapify(arr,0,j);
        }
    }

    //维护堆(大顶堆，用于升序),length--数组长度指针，递归方式
    private void heapify(int[] arr,int index,int length){
        int biggest = index,
            leftChild = index*2+1,
            rightChild = index*2+2;
        if (leftChild<length && arr[leftChild]>arr[biggest]){
            biggest = leftChild;
        }
        if (rightChild<length && arr[rightChild]>arr[biggest]){
            biggest = rightChild;
        }

        if (biggest!=index){
            swap(arr,index,biggest);
            heapify(arr,biggest,length);
        }
    }

    private static void swap(int[] arr, int index1, int index2){
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

    public static void main(String[] args) {
        int arr1[] = new int[]{4, 2, 1, 5, 7, 11, 32, 43, 22, 15}, arr2[] = new int[]{3,3,3,7,9,122344,4656,34,34,4656,5,6,7,8,9,343,57765,23,12321};

        HeapSort heapSort = new HeapSort();

//        heapSort.sort(arr2);
//        System.out.println(Arrays.toString(arr2));

        heapSort.sort(arr1);
        System.out.println(Arrays.toString(arr1));
    }

    //循环方式，维护两个指针 i--根节点，k--根节点的最大子节点
    public static void adjustHeap(int[] array, int i, int length) {
        // 先把当前元素取出来，因为当前元素可能要一直移动
        int temp = array[i];
        for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {  //2*i+1为左子树i的左子树(因为i是从0开始的),2*k+1为k的左子树
            // 让k先指向子节点中最大的节点
            if (k + 1 < length && array[k] < array[k + 1]) {  //如果有右子树,并且右子树大于左子树
                k++;
            }
            //如果发现结点(左右子结点)大于根结点，则进行值的交换
            if (array[k] > temp) {
                swap(array, i, k);
                // 如果子节点更换了，那么，以子节点为根的子树会受到影响,所以，循环对子节点所在的树继续进行判断
                i  =  k;
            } else {  //不用交换，直接终止循环
                break;
            }
        }
    }
}
